package Leetcode.动态规划;

/**
 * @Author: kirito
 * @Date: 2024/4/5 13:34
 * @Description:
 * 最大正方形
 *
 * 一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：4
 * 示例 2：
 *
 *
 * 输入：matrix = [["0","1"],["1","0"]]
 * 输出：1
 * 示例 3：
 *
 * 输入：matrix = [["0"]]
 * 输出：0
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 300
 * matrix[i][j] 为 '0' 或 '1'
 */

public class maximalSquare {
    /**
     * dp[i][j]  代表
     * i j为奇数肯定不是正方形
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        // 初始化最大边长为0
        int maxSide = 0;
        // 如果矩阵为空或者长度为0，返回0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        // 获取矩阵的行数和列数
        int rows = matrix.length, columns = matrix[0].length;
        // 创建一个二维数组，用于存储每个位置上可以构成的最大正方形的边长
        int[][] dp = new int[rows][columns];
        // 遍历矩阵的每个位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                // 如果当前位置的元素为'1'
                if (matrix[i][j] == '1') {
                    // 如果处于第一行或者第一列，则正方形的边长为1
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        // 否则，正方形的边长是上方、左方和左上方的最小值加1
                        //这个表达式很巧妙，最开始我的逻辑想法是需要判断左上，上，左三个地方的值
                        //且需要考虑很多中情况，但是没有总结出一种方便统计的办法
                        //穷举情况来写的话代码逻辑很复杂冗余，这样根据Min去求的话刚好完美符合我的逻辑
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    // 更新最大边长
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        // 返回最大边长的平方，即可以构成的最大正方形的面积
        return maxSide * maxSide;
    }

    //暴力
    public int maximalSquare2(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}
